The Basic Evaltrace Notation

Evaluation in Lisp proceeds according to a set of evaluation rules built into the EVAL and APPLY functions. Evaluation of the simple expression (+ 2 3) employs two of these rules. First, numbers evaluate to themselves. Second, to evaluate a list describing a function call, one first evaluates the arguments to the function, and then applies the function to the evaluated arguments. This leads to the evaltrace of (+ 2 3) shown below. Thin lines represent calls to EVAL, and thick lines calls to APPLY.


\begin{evaltrace} +--> ;(++ 2 3) \vert \vert +--> ;2 {\it First argument evaluat... ... to 2 and 3 {\it Apply the function to its arguments.} * +_*> ;5 \end{evaltrace}

Often we will want to suppress some details, such as the evaluation of trivial arguments to a function, or the application of a primitive like +. In that case, the above evaluation is depicted this way:


\begin{evaltrace} +--> ;(++ 2 3) \vert +_-> ;5 \end{evaltrace}

When an evaltrace diagram is elided like this to a single application of EVAL, it is equivalent to the simple evaluation arrow used in [4] and most other books on Lisp:


\begin{code} (+ 2 3) {\et -->} 5 \end{code}

The real power of evaltrace notation becomes apparent when we consider the application of non-primitive functions, since these may create local variables and call other functions from within their bodies. The function DOUBLE below creates a local variable N to hold its argument, and calls the primitive function * to compute its result. (All of the examples in this paper are written in Common Lisp.)


\begin{code} (defun double (n) (* n 2)) \end{code}

An evaltrace of the expression (double (+ 3 5)) shows how a local variable is created inside the body of DOUBLE to hold the evaluated argument.


\begin{evaltrace} +--> ;(double (++ 3 5)) \vert \vert +--> ;(++ 3 5) \vert \vert... ...'' * \vert ''2''-->''2'' * +_-> ;16 +_*> ;Result of DOUBLE is 16 \end{evaltrace}

This example involves the evaluation of the symbol N. The evaluation rule for symbols is that they evaluate to the value of the variable which they name. In earlier Lisp dialects people would speak of symbols themselves being variables or having values, but this is not appropriate in Scheme or Common Lisp since several variables with the same name may exist simultaneously in different lexical contexts. The symbol N appearing in the body of DOUBLE refers to the local variable N that is created when DOUBLE is applied. Outside the body of DOUBLE, the symbol N does not refer to this variable. The fact that this is a textual property of the program is important, as it means that illegal references to N can easily be caught by a compiler, before calls to DOUBLE are actually evaluated.

When DOUBLE is applied, a lexical contour is created in which the variable named N resides. In the evaltrace diagram, the thick line marking the application of DOUBLE shows the boundaries of this lexical contour. Only thick lines denote lexical contours. Thin lines, which represent calls to EVAL, do not denote contours. This distinction is an important part of the scoping of Lisp programs, which will be discussed later.

It is easy to forget that lexical contours are created only when a function is applied, not when it is defined. If DOUBLE were to be applied five times, five distinct lexical contours, each with its own variable named N, would be created. Consider the following function:


\begin{code} (defun quintuple (n) (+ (double (double n)) n)) \end{code}

Figure: Evaltrace diagram illustrating the creation of contours.
\begin{figure}{\noindent\rule{\textwidth}{.01in}} \par \begin{evaltrace} +--> ;(... ...is 25 \end{evaltrace}\par\par {\noindent\rule{\textwidth}{.01in}} \end{figure}

Both DOUBLE and QUINTUPLE, when applied, create local variables named N. Because of lexical scoping, QUINTUPLE's N is distinct from DOUBLE's N. Furthermore, each of the two applications of DOUBLE creates a new variable referred to by the name N. This can be seen in the evaltrace diagram given in Figure [*], where three distinct lexical contours are shown (not counting the one for +), each containing a variable named N. These variables are independent. Thus, the value of N in QUINTUPLE's contour remains 5, even after the second call to DOUBLE assigns the value 10 to a (distinct) variable which is also named N.

Every lexical contour has a parent contour, except that global variables exist in a top-level contour (also called the global contour) that has no parent. Consider the function CIRCUMFERENCE that references a global variable CRUDE-PI: (SETF is the general assignment operator in Common Lisp.)


\begin{code} (setf crude-pi 3.14) \strut (defun circumference (r) (* 2 r crude-pi)) \end{code}


\begin{evaltrace} +--> ;(circumference 5) \vert +**> ;Apply CIRCUMFERENCE to 5 *... ...''-->''3.14'' * +_-> ;31.4 +_*> ;Result of CIRCUMFERENCE is 31.4 \end{evaltrace}

The rules for mapping symbols to the variables which they name are called scope rules. When evaluating the symbol R in the body of CIRCUMFERENCE, the first scope rule tells us to look in the current lexical contour for a variable with that name. Since there is a local variable named R created by CIRCUMFERENCE, the symbol R is treated as a reference to that variable. But in the case of CRUDE-PI, there is no local variable by that name in the current contour. Consequently, the rules for lexical scoping tell us to look in the parent contour, which happens to be the global contour (which is also the only other contour in this example). A variable named CRUDE-PI does exist in the global contour, so the symbol CRUDE-PI is taken to refer to that variable.

The difference between lexical and dynamic scoping disciplines is in the way parent contours are determined. We will return to this topic shortly.